题解 P2151 【[SDOI2009]HH去散步】

发表于 | 更新于

题意:HH有个一成不变的习惯，喜欢饭后百步走。所谓百步走，就是散步，就是在一定的时间 内，走过一定的距离。 但是同时HH又是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。 又因为HH是个喜欢变化的人，所以他每天走过的路径都不完全一样，他想知道他究竟有多 少种散步的方法。

现在给你学校的地图（假设每条路的长度都是一样的都是$1$），问长度为$t$，从给定地 点$A$走到给定地点$B$共有多少条符合条件的路径

如果没有限制条件不能沿着刚走过的道路走回，那就是裸的矩阵快速幂优化$DP$了。

但是，这个限制条件使得无论怎么构造矩阵，普通的矩阵快速幂不能符合要求

这时，我们就要向别的方向想了，普通的矩阵快速幂是点之间转移，那我们能不能边与边之间转移呢$？$

只需要在矩阵中将除了当前边与当前边的反向边以外的所有边对的权值都赋为$1$,然后进行矩阵快速幂即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
#define int long long
#define mod 45989
using namespace std;
struct ed{
    int u,v;
}e[393939];
int cnt,ans,n,m,t,A,B;
struct node{
    int a[207][207];
    inline void init0(){memset(a,0,sizeof(a));}
    inline void init1(){
        memset(a,0,sizeof(a));
        for (int i=0;i<=n;++i)
            for (int j=0;j<=n;++j)
                a[i][j]=i==j;
    }
    friend node operator *(node a,node b){
        node res;res.init0();
        for (int i=0;i<=n;++i)
            for (int k=0;k<=n;++k)
                for (int j=0;j<=n;++j){
                    res.a[i][k]=(res.a[i][k]+a.a[i][j]*b.a[j][k]%mod)%mod;
                }
        return res;
    }
    friend node operator ^(node x,int p){
        node res;res.init1();
        while (p>0){
            if (p&1)res=res*x;
            x=x*x;
            p>>=1;
        }
        return res;
    }
}f;
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
signed main(){
//    freopen("desire.in","r", stdin); freopen("desire.out", "w", stdout); 
    cnt=read(),m=read(),t=read(),A=read(),B=read();
    f.init0();n=-1;
    for (int i=1;i<=m;++i){
        int u=read(),v=read();
        e[++n]=(ed){u,v};
        e[++n]=(ed){v,u};
    }
    for (int i=0;i<=n;++i)
        for (int j=0;j<=n;++j)
            if ((i!=j)&&((i^1)!=j)&&(e[i].v==e[j].u))
                f.a[i][j]=1;
    f=f^(t-1);
    for (int i=0;i<=n;++i)
        if (e[i].u==A)
            for (int j=0;j<=n;++j)
                if (e[j].v==B)
                    ans=(ans+f.a[i][j])%mod;
    printf("%d",ans);
}